翻訳と辞書 Words near each other ・ Locally finite collection ・ Locally finite group ・ Locally finite measure ・ Locally finite operator ・ Locally finite poset ・ Locally finite space ・ Locally finite variety ・ Locally Hausdorff space ・ Locally integrable function ・ Locally listed buildings in Crawley ・ Locally nilpotent ・ Locally normal space ・ Locally profinite group ・ Locally regular space ・ Locally simply connected space ・ Locally testable code ・ Locally unwanted land use ・ Locals casino ・ LocalSaver.com ・ LocalTalk ・ LocalTalk-to-Ethernet bridge ・ LocalVision ・ LocalWiki ・ Locana ・ Locanda Locatelli ・ Locans, California ・ Locant ・ Locanto ・ Locard ・ Locard's exchange principle Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Locally testable code ： ウィキペディア英語版 Locally testable code A locally testable code is a type of error-correcting code for which it can be determined if a string is a word in that code by looking at a small (frequently constant) number of bits of the string. In some situations, it is useful to know if the data is corrupted without decoding all of it so that appropriate action can be taken in response. For example, in communication, if the receiver encounters a corrupted code, it can request the data be re-sent, which could increase the accuracy of said data. Similarly, in data storage, these codes can allow for damaged data to be recovered and rewritten properly. In contrast, locally decodable codes use a small number of bits of the codeword to probabilistically recover the original information. The fraction of errors determines how likely it is that the decoder correctly recovers the original bit; however, not all locally decodable codes are locally testable. Clearly, any valid codeword should be accepted as a codeword, but strings that are not codewords could be only one bit off, which would require many (certainly more than a constant number) probes. To account for this, testing failure is only defined if the string is off by at least a set fraction of its bits. This implies words of the code must be longer than the input strings by adding some redundancy. == Definition == To measure the distance between two strings, the Hamming distance is used :$\backslash Delta(x,y)=|\backslash |$ The distance of a string $w$ from a code $C:\backslash ^k\backslash to\backslash ^n$ is computed by :$\backslash Delta(w,C)=\backslash min\_x\backslash$ Relative distances are computed as a fraction of the number of bits :$\backslash delta(x,y)=\backslash Delta(x,y)/n\; \backslash text\; \backslash delta(w,C)=\backslash Delta(w,C)/n$ A code $C:\backslash ^k\backslash to^n$ is called $q$-local $\backslash delta$-testable if there exists a Turing machine M given random access to an input $w$ that makes at most $q$ non-adaptive queries of $w$ and satisfies the following: : * For any $x\backslash in\backslash ^k$ and $w=C(x)$, $Pr()=1$. In other words, M accepts given access to any codeword of C. : * For $w\backslash in\backslash ^n$ such that $\backslash delta(w,C)>\backslash delta$, $Pr()\backslash leq1/2$. M must reject strings $\backslash delta$-far from C at least half the time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Locally testable code」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.